BZOJ1004【HNOI2008】Cards < Burside引理+背包DP >

Problem

【HNOI2008】Cards

Description

小春现在很清闲，面对书桌上的张牌，他决定给每张染色。
目前小春只有种颜色：红色，蓝色，绿色。他询问有多少种染色方案，很快就给出了答案。
进一步，小春要求染出张红色，张蓝色，张绿色。他又询问有多少种方案，想了一下，又给出了正确答案。
最后小春发明了种不同的洗牌法，他又问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
发现这个问题有点难度，决定交给你。
答案可能很大，只要求出答案除以的余数（为质数）。

Input

第一行输入个整数：。。
接下来行，每行描述一种洗牌法，每行有个用空格隔开的整数，恰为到的一个排列，表示使用这种洗牌法，第位变为原来的位的牌。
数据保证任意多次洗牌都可用种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

Output

不同染法除以的余数。

Sample Input

1
2
3

1 1 1 2 7
2 3 1
3 1 2

Sample Output

Explanation

有种本质上不同的染色法RGB和RBG，使用洗牌法231一次可得GBR和BGR，使用洗牌法312一次可得BRG和GRB。

HINT

数据满足。

标签：Burnside引理 背包DP

Solution

挺好的一道群论基础题，一看是定理裸题，再看发现要转化为背包数不动点。

将每一种洗牌方式看成一种置换，这些置换所形成的群称为。将所有排列的集合称为。那么对于群在集合上的作用，我们想计算其无交轨道数，即。
对于一个置换，令，即关于的轨道上的不动点数目。
由引理可知，有

由于题目中对每种颜色的数量都有限制，我们无法直接套用定理，因此只能按照引理将每种置换对应的轨道上不动点数的和算出来，再计算。

考虑对于一种置换（洗牌方式），如何计算其不动点数。
首先，对于一个置换，我们一定可以将其表示为若干轮换作用起来的形式。
例如，对于置换

我们可以将其分为不相关的两部分

再写成两个轮换相作用的形式

由于每个轮换内部都可以任意交换，对于一种置换，其不动点的每个轮换内部一定是涂的相同颜色。这意味着我们可以将一个轮换作为一个整体看待。
于是我们预处理出这个置换每个轮换的大小，将一个轮换看作大小为其长度的物品，做背包。
设第个物品大小为。用表示前个物品，有个是第种颜色，有个是第种颜色，此状态下的染色方案数。那么染第种颜色的物品数为。有三种转移：

若，则
若，则
若，则

对于每个输入的洗牌方式，先求出数组，再求出不动点个数并累加即可得到总不动点个数。注意这里还需要加上恒等置换（即所有位置都不动）的不动点数，即。
答案等于。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, A, B, C, num;
int p[65], cnt[65], tot[65];
lnt f[65][65][65], pw[65], P;
bool mrk[65];
lnt inv(lnt x) {
    lnt ret = 1;
    for (lnt k = P-2; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
void DFS(int u, int sz) {
    if (mrk[u]) {cnt[++num] = sz; return;}
    mrk[u] = true, DFS(p[u], sz+1);
}
int main() {
    read(A), read(B), read(C), n = A+B+C, read(m), read(P);
    pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i-1]*i%P;
    lnt sum = pw[n]*inv(pw[A])%P*inv(pw[B])%P*inv(pw[C])%P;
    for (int T = 1; T <= m; T++) {
        num = 0; memset(mrk, false, sizeof mrk);
        for (int i = 1; i <= n; i++) read(p[i]);
        for (int i = 1; i <= n; i++) if (!mrk[i]) DFS(i, 0);
        for (int i = 1; i <= num; i++) tot[i] = tot[i-1]+cnt[i];
        for (int i = 1; i <= num; i++)
            for (int a = 0; a <= A; a++)
                for (int b = 0; b <= B; b++) {
                    int c = tot[i]-a-b; f[i][a][b] = 0;
                    if (a >= cnt[i]) (f[i][a][b] += f[i-1][a-cnt[i]][b]) %= P;
                    if (b >= cnt[i]) (f[i][a][b] += f[i-1][a][b-cnt[i]]) %= P;
                    if (c >= cnt[i]) (f[i][a][b] += f[i-1][a][b]) %= P;
                }
        (sum += f[num][A][B]) %= P;
    }
    return printf("%lld\n", sum*inv(m+1)%P), 0;
}